class UnionFind:
    """并查集（Disjoint Set Union）实现"""
    def __init__(self, size):
        self.parent = list(range(size))  # 初始化每个节点的父节点为自己
        self.rank = [1] * size  # 初始化每个节点的秩为 1

    def find(self, x):
        """查找节点的根节点（路径压缩优化）"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        """合并两个集合（按秩合并优化）"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True  # 合并成功
        return False  # 已经在同一个集合中

def kruskal(graph):
    """Kruskal 算法实现"""
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((weight, u, v))  # 存储边及其权重
    edges.sort()  # 按权重从小到大排序

    uf = UnionFind(len(graph))  # 初始化并查集
    mst = []  # 存储最小生成树的边
    total_weight = 0  # 最小生成树的总权重

    for weight, u, v in edges:
        if uf.union(u, v):  # 如果两个顶点不在同一个集合中
            mst.append((u, v, weight))  # 将边加入最小生成树
            total_weight += weight
            if len(mst) == len(graph) - 1:  # 如果边数达到 V-1，结束
                break

    return mst, total_weight

# 示例图（邻接表表示）
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

# 运行 Kruskal 算法
mst, total_weight = kruskal(graph)
print("最小生成树的边：", mst)
print("最小生成树的总权重：", total_weight)
